import heapq as hq
class Solution:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def add_num(self, num):
        # 1. all elements in the max heap must be smaller than the ones in the min heap
        hq.heappush(self.max_heap, (-num, num))
        val = hq.heappop(self.max_heap)[1]
        hq.heappush(self.min_heap, (val, val))
        # 2. the max heap contains at least the number of elements as in the min heap
        while len(self.max_heap) < len(self.min_heap):
            val = hq.heappop(self.min_heap)[1]
            hq.heappush(self.max_heap, (-val, val))

    def median(self):
        if len(self.max_heap) == len(self.min_heap):
            return (self.max_heap[0][1] + self.min_heap[0][1])/2
        else:
            return self.max_heap[0][1]

sol = Solution()
sol.add_num(1)
sol.add_num(2)
print(sol.median())
sol.add_num(3)
print(sol.median())